package 二叉树相关问题.中度题;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class 输出二叉树 {

    public List<List<String>> printTree(TreeNode root) {
        List<List<String>> lists = new LinkedList<>();
        if (root==null)
               return lists;
        int depth = maxDepth(root);
        int r =(int)Math.pow(2, depth) - 1;
        String[][] res = new String[depth][r];
        for (String[] arr : res) {
            Arrays.fill(arr,"");
        }
        method(res,root,0,0,r);
        for (String[] arr : res) {
            lists.add(Arrays.asList(arr));
        }
        return lists;
    }

    private void method(String[][] res, TreeNode root, int depth, int l, int r) {
        if (root==null)
            return;
        int mid=(l+r)/2;
        res[depth][mid]=""+root.val;
        method(res,root.left,depth+1,l,mid);
        method(res,root.right,depth+1,mid,r);
    }

    //找树的最大深度
    public static int maxDepth(TreeNode root){
        if (root==null)
            return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        return 1+Math.max(left,right);
    }
}
